package Tree;

import javax.sound.midi.Soundbank;
import java.awt.*;

/**
 * @author yyq
 * @create 2022-01-11 11:04
 *
 * 二叉排序树
 *
 */
public class BinarySortTree {
    public static void main(String[] args) {
        int[] array = {7, 3, 10, 12, 5, 1, 9,2};
        Node root = BST(array);
        inOrder(root);
        System.out.println();
        deleteNode(7,-1,null,root);
        inOrder(root);
    }

    public static void deleteNode(Integer delData,Integer direction,Node parent,Node now){
        if(now.data==delData){
            //情况1 now为叶子结点
            if(now.right==null&&now.left==null){
                if(direction==0){
                    parent.left=null;
                }
                if(direction==1){
                    parent.right=null;
                }
                return;
            }

            //情况2.1 now节点下有一个左孩子
            if(now.right==null&&now.left!=null){
                //判断 now在parent的位置
                if(direction==0){
                    parent.left=now.left;
                }
                if(direction==1){
                    parent.right=now.left;
                }
                return;
            }

            //情况2.2 now节点下有一个右孩子
            if(now.right!=null&&now.left==null){
                //判断 now在parent的位置
                if(direction==0){
                    parent.left=now.right;
                }
                if(direction==1){
                    parent.right=now.right;
                }
                return;
            }

            //情况3 now节点下有两个孩子
            if(now.right!=null&&now.left!=null){

                // now为parent的孩子 需要找到 now左子树最右边的节点来替换now
                Node temp=now.left;
                Node fir = null;
                while(temp.right!=null){
                    if(temp.right.right==null) fir=temp;
                    temp=temp.right;
                }
                // temp肯定无右孩子
                // 假设temp有左孩子
                if(temp.left!=null){
                    Integer tempData = temp.data;
                    temp.data=temp.left.data;
                    temp.left=null;
                    now.data=tempData;
                }
                //假设temp无左孩子
                if(temp.left==null){
                    fir.right=null;
                    now.data=temp.data;
                }
                return;

            }

        }
        if(now.left!=null)
            deleteNode(delData,0,now,now.left);
        if(now.right!=null)
            deleteNode(delData,1,now,now.right);

    }

    public static void inOrder(Node root){

        if(root.left!=null){
            inOrder(root.left);
        }

        System.out.println(root.data);

        if(root.right!=null){
            inOrder(root.right);
        }
    }

    public static Node BST(int[] a){
        int len = a.length;
        Node root=new Node(a[0]);
        for (int i = 1; i < len; i++) {
            Node temp = root;
            while(temp!=null){
                if(a[i]>= temp.data&&temp.right==null){
                    temp.right = new Node(a[i]);
                    break;
                }

                if(a[i]< temp.data&&temp.left==null){
                    temp.left = new Node(a[i]);
                    break;
                }


                if(a[i]>=temp.data&&temp.right!=null){
                    temp = temp.right;
                    continue;
                }

                if(a[i]<temp.data&&temp.left!=null){
                    temp = temp.left;
                    continue;
                }

            }
        }
        return root;
    }

}


class Node{
    Integer data;
    Node left;
    Node right;

    public Node(Integer data) {
        this.data = data;
    }

    @Override
    public String toString() {
        return "Node{" +
                "data=" + data +
                '}';
    }
}
